package org.shj.algorithm.string;

/**
 * 最长递增子序列(LIS)问题
 * 如一个数组是 [5, 6, 7, 1, 3, 8], 其 LIS 是 5,6,7,8  长度是 4
 *
 * 解题思路：
 *  方法一： 把原数组 A 从小到大排序得到 B，则 A 和 B 的 LCS 即为所求解
 *
 *  方法二. 动态规划
 *  1. 设数组为 a[n], 且 f[i] 为以第 i 项结尾的 LIS 的长度
 *  2. 若存在 j < i 且 a[j] < a[i]， 则 f[i] = f[j] + 1
 *
 * @author Shen Huang Jian
 * @date 2019-01-23 12:13
 */
public class LongestIncreasingSubsequence {

    public static void main(String[] args){
        //动态规划方法

        int[] a = {15, 40, 50, 60, 20, 10, 70, 80};
        int[] f = new int[a.length];

        // 以第一个结尾的 LIS，就是只有其本身
        f[0] = 1;

        for(int i = 1 ; i < a.length; i++){
            // 循环判断在 i 前是否存在 j
            for(int j = 0; j < i; j++){
                if(a[j] < a[i]){
                    //可能有不止一个a[j] < a[i]，所以 f[i] 需要取最大的一个
                    if(f[i] <= f[j]){
                        f[i] = f[j] + 1;
                    }
                }
            }
        }

        int max = 1;
        int index = 0;
        for(int i = 0; i < a.length; i++){
            if(f[i] > max){
                max = f[i];
                index = i;
            }
        }

        //可能存在多个解，此处只能打印一个解
        int current = f[index];
        String out = a[index] + "";
        for(int i = index - 1; i >= 0; i--){
            if(f[i] == current - 1){
                out = a[i] + ", " + out;
                current--;
            }
        }
        System.out.println(out);
    }
}
